"""
题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。
滑动窗口每次只向右移动一位。返回每次滑动窗口中的最大值构成的集合。
示例说明：
对于输入[1,3,-1,-3,5,3,6,7]和 k=3
第一个窗口[1,3,-1]的最大值是 3
第二个窗口[3,-1,-3]的最大值是 3
第三个窗口[-1,-3,5]的最大值是 5
......
以此类推，最终得到并返回的结果是集合：[3,3,5,5,6,7]

"""

from collections import deque
'''
解题思路：
通过双端队列维护“窗口内可能的最大值候选”：队列尾部弹出小于当前元素的索引，保证队列递减；队列头部弹出超出窗口范围的索引，保证候选有效；
当窗口形成后，队首元素就是当前窗口的最大值。最终时间复杂度为O(n)（每个元素最多入队、出队各一次），是解决 “滑动窗口最大值” 的高效方法。
'''
def maxSlidingWindow(nums, k):
    # 处理特殊情况
    if not nums or k == 0:
        return []
    # 双端队列，用于存储元素的索引，保持队列中元素对应的数值递减
    q = deque()
    # 结果列表
    result = []
    # 遍历数组   enumerate(nums) 会同时遍历数组 nums 的索引（i）和对应元素值（num）。
    for i, num in enumerate(nums):
        #当队列不为空，且队列尾部索引对应的数组元素小于当前元素 num 时，不断弹出队列尾部元素。
        #目的：维护队列的 “递减性”—— 队列中存储的索引对应的数组元素，从队首到队尾是递减的。这样队首元素始终是当前窗口的最大值对应的索引。
        while q and nums[q[-1]] < num:
            q.pop()
        # 将当前元素索引加入队列 作用：当前元素成为窗口的候选最大值，后续窗口滑动时，它可能成为某个窗口的最大值。
        q.append(i)
        # 当队列头部的索引 超出当前窗口的左边界 时，弹出队首元素。 目的：保证队列中的索引都在当前窗口范围内，避免使用过期的 “最大值候选”。
        while q[0] <= i - k:
            q.popleft()
        # i >= k - 1 表示窗口已经形成（前 k 个元素处理完后，窗口开始滑动）
        #nums[q[0]] 是队列头部索引对应的数组元素，由于队列是递减的，所以这是当前窗口的最大值。
        #作用：将每个窗口的最大值加入结果列表 result。
        if i >= k - 1:
            result.append(nums[q[0]])
    return result
# 测试示例
print(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3,3,5,5,6,7]